Search results for "Continuous spatial automaton"
showing 10 items of 15 documents
Research of Complex Forms in Cellular Automata by Evolutionary Algorithms
2004
This paper presents an evolutionary approach for the search for new complex cellular automata. Two evolutionary algorithms are used: the first one discovers rules supporting gliders and periodic patterns, and the second one discovers glider guns in cellular automata. An automaton allowing us to simulate AND and NOT gates is discovered. The results are a step toward the general simulation of Boolean circuits by this automaton and show that the evolutionary approach is a promising technic for searching for cellular automata that support universal computation.
Running time to recognize nonregular languages by 2-way probabilistic automata
1991
R. Freivalds proved that the language {0m1m} can be recognized by 2-way probabilistic finite automata (2pfa) with arbitrarily high probability 1-ɛ. A.G.Greenberg and A.Weiss proved that no 2pfa can recognize this language in expected time \(T(n) = c^\circ{(n)}\). For arbitrary languages C.Dwork and L.Stockmeyer showed somewhat less: if a language L is recognized by a 2pfa in expected time \(T(n) = c^{n^\circ{(1)} }\), then L is regular. First, we improve this theorem replacing the expected time by the time with probability 1-ɛ. On the other hand, time bound by C.Dwork and L.Stockmeyer cannot be improved: for arbitrary k≥2 we exhibit a specific nonregular language that can be recognized by 2…
Transition Function Complexity of Finite Automata
2011
State complexity of finite automata in some cases gives the same complexity value for automata which intuitively seem to have completely different complexities. In this paper we consider a new measure of descriptional complexity of finite automata -- BC-complexity. Comparison of it with the state complexity is carried out here as well as some interesting minimization properties are discussed. It is shown that minimization of the number of states can lead to a superpolynomial increase of BC-complexity.
Quantum Finite State Automata over Infinite Words
2010
The study of finite state automata working on infinite words was initiated by Buchi [1]. Buchi discovered connection between formulas of the monadic second order logic of infinite sequences (S1S) and ω-regular languages, the class of languages over infinite words accepted by finite state automata. Few years later, Muller proposed an alternative definition of finite automata on infinite words [4]. McNaughton proved that with Muller’s definition, deterministic automata recognize all ω-regular languages [2]. Later, Rabin extended decidability result of Buchi for S1S to the monadic second order of the infinite binary tree (S2S) [5]. Rabin theorem can be used to settle a number of decision probl…
Language Recognition Power and Succinctness of Affine Automata
2016
In this work we study a non-linear generalization based on affine transformations of probabilistic and quantum automata proposed recently by Diaz-Caro and Yakaryilmaz [6] referred as affine automata. First, we present efficient simulations of probabilistic and quantum automata by means of affine automata which allows us to characterize the class of exclusive stochastic languages. Then, we initiate a study on the succintness of affine automata. In particular, we show that an infinite family of unary regular languages can be recognized by 2-state affine automata, whereas the number of states of any quantum and probabilistic automata cannot be bounded. Finally, we present the characterization …
One Alternation Can Be More Powerful Than Randomization in Small and Fast Two-Way Finite Automata
2013
We show a family of languages that can be recognized by a family of linear-size alternating one-way finite automata with one alternation but cannot be recognized by any family of polynomial-size bounded-error two-way probabilistic finite automata with the expected runtime bounded by a polynomial. In terms of finite automata complexity theory this means that neither 1Σ2 nor 1Π2 is contained in 2P2.
Hopcroft's algorithm and tree-like automata
2011
Minimizing a deterministic finite automata (DFA) is a very important problem in theory of automata and formal languages. Hopcroft's algorithm represents the fastest known solution to the such a problem. In this paper we analyze the behavior of this algorithm on a family binary automata, called tree-like automata, associated to binary labeled trees constructed by words. We prove that all the executions of the algorithm on tree-like automata associated to trees, constructed by standard words, have running time with the same asymptotic growth rate. In particular, we provide a lower and upper bound for the running time of the algorithm expressed in terms of combinatorial properties of the trees…
Quantum Finite Multitape Automata
1999
Quantum finite automata were introduced by C. Moore, J. P. Crutchfield [4], and by A. Kondacs and J. Watrous [3]. This notion is not a generalization of the deterministic finite automata. Moreover, in [3] it was proved that not all regular languages can be recognized by quantum finite automata. A. Ambainis and R. Freivalds [1] proved that for some languages quantum finite automata may be exponentially more concise rather than both deterministic and probabilistic finite automata. In this paper we introduce the notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite automaton but not by deterministic or probabilistic finite automata. This …
Probabilistic Reversible Automata and Quantum Automata
2002
To study relationship between quantum finite automata and probabilistic finite automata, we introduce a notion of probabilistic reversible automata (PRA, or doubly stochastic automata). We find that there is a strong relationship between different possible models of PRA and corresponding models of quantum finite automata. We also propose a classification of reversible finite 1-way automata.
Group Input Machine
2009
We introduce a new type of internal memory for finite automata and real-time automata. Instead of using tapes with a prescribed Euclidean structure (one-dimensional or two-dimensional tapes) we allow arbitrary group structure of the internal memory of the automata.